package day_2022_4_to_7.day48;

import java.util.Scanner;

/**
 * 斐波那契凤尾
 * @author haomin
 * @date 2022/05/31 10:53
 **/

// 时间复杂度过高
public class Day32_2_fib {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            int n = in.nextInt();
            long[] dp = new long[n+1];
            dp[0] = 1;
            dp[1] = 1;
            for (int i = 2; i <= n; i++) {
                dp[i] = dp[i-1] + dp[i-2];
            }
            long num = dp[n];

            if(num < 1000000){
                System.out.println(num);
            }else {
                StringBuilder ret = new StringBuilder();
                int count = 6;
                while (count-- >0){
                    ret.append(num % 10);
                    num /= 10;
                }
                System.out.println(ret.reverse());
            }
        }
    }
}

// 这个ok
class Main2{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[] fib = new int[100001];
        fib[0] = 1;
        fib[1] = 1;
        for(int i = 2; i < fib.length; i++){
            fib[i] = (fib[i-1]+fib[i-2])%1000000;
        }
        while(sc.hasNext()){
            int n = sc.nextInt();
            //因为牛客的“严谨”，不得不%06d
            System.out.printf((n<25 ? "%d\n":"%06d\n"), fib[n]);
        }
    }
}